paste_lycszzay

注意:本页面是由自动化程序生成的剪贴板存档。

#include <cstdio>
void swap(int& a, int& b) {
	int t = a;
	a = b;
	b = t;
}
#define N 1000000
int a[N], b[N]; bool u[N];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {u[i] = false; b[i] = i; }
	int l = 0, r = n, f = 0;
	for (int i = 0; i < n; i++) {
		int mid = (l+r)/2;
		u[b[mid]] = true;
		if (b[mid] == f) {
			a[b[mid]] = l+1; // <--
			swap(b[l++], b[mid]);
			while (f < r && u[f]) f++;
		} else {
			a[b[mid]] = r;
			swap(b[l], b[mid]);
			swap(b[l], b[--r]);
		}
	}
	for (int i = 0; i < n; i++) printf("%d ", a[i]);
	puts("");
}